Least Squares Problem

$A\vec{x}=\vec{b}$의 해가 존재하지 않을 때, 즉, $b\notin ColA$ 일 때, 최대한 적은 error를 가져오는 해를 찾는 문제.

A least squares solution $\hat{\vec{x}}$ is defined as

즉, $b$에서 $Ax$를 뺀 값이, 가장 작은 크기(vector 차의 제곱)로 구해질 때를 얻어온다.

이 때 제일 작은 거리는, $\hat{\vec{b}}$가 존재하는, 즉 b에서 $ColA$에 수직인 면에 존재하는 점일 때, 그 거리가 제일 짧게 되므로, $||\vec{b}-A\vec{x}||$의 크기가 제일 작아진다.

Inner product

---

이는, $A$와 $\vec{b}-A\hat{\vec{x}}$가 수직임을 의미하므로, 두 행렬을 Inner Product 했을 때, 0이 나옴을 의미한다.

$$A^{\top }(b-A\hat{\vec{x}})=0$$

• Normal Equation: $A^{\top }A\hat{\vec{x}}=A^{\top }\vec{b}$
• $A^{\top }A$ is invertible, solution will be

: Pseudo Inverse Matrix로 볼 수도 있다.

Another Variation

---

• $\hat{\vec{x}}=\arg {\min }_x||\vec{b}-A\vec{x}||=\arg {\min }_x||\vec{b}-A\vec{x}|{|}^2$
• $(b-Ax{)}^{\top }(b-Ax)=b^{\top }b-x^{\top }{A}^{\top }b-b^{\top }Ax-x^{\top }{A}^{\top }Ax$
• derivation: use derivation of mutiplied function
• $f(x)=a^{\top }x=x^{\top }a$ : $f^{\prime }(x)=a$

If $A^{\top }A$ is NOT Invertible?

---

수선의 발은, 항상 존재한다. 즉, $\hat{\vec{b}}$를 나타내는 Linear Combination이 가능한 계수가 무수히 많이 존재하는 경우 밖에 존재하지 않으며, 해가 없는 경우는 없다.

Not Invertible한 경우라면, $A$가 Linear Independent 하지 않은 경우이다.